package com.lsa.skienna.challenge.chap8;

public class permuts {
	static boolean finished = false;
	static final int MAXCANDIDATES = 100;
	static final int NMAX = 100;

	static void backtrack(int[] partialSolution, int partialSolutionSize,
			int fullSolutionSize) {
		if (is_a_solution(partialSolution, partialSolutionSize,
				fullSolutionSize))
			process_solution(partialSolution, partialSolutionSize,
					fullSolutionSize);
		else {
			int solutionCandidates[] = new int[MAXCANDIDATES];
			int solutionCandidatesSize = construct_candidates(partialSolution,
					partialSolutionSize, fullSolutionSize, solutionCandidates);
			for (int i = 0; i < solutionCandidatesSize; i++) {
				partialSolution[partialSolutionSize] = solutionCandidates[i];
				backtrack(partialSolution, partialSolutionSize + 1,
						fullSolutionSize);
				if (finished)
					return;
			}
		}
	}

	static void make_move(int[] a, int k, int n) {
	}

	static void unmake_move(int[] a, int k, int n) {
	}

	static void process_solution(int[] a, int k, int n) {
		for (int i = 0; i < k; i++)
			System.out.printf(" %d", a[i]);

		System.out.printf(" \n");
	}

	static boolean is_a_solution(int[] partialSolution, int partialSolutionSize, int fullSolutionSize) {
		return partialSolutionSize == fullSolutionSize;
	}

	static int construct_candidates(int[] partialSolution, int partialSolutionSize, int fullSolutionSize, int[] solutionCandidates) {
		int l = 0;
		boolean[] inPerm = new boolean[MAXCANDIDATES];
		for (int i = 0; i < partialSolutionSize; i++) {
			inPerm[partialSolution[i]] = true;
		}
		for (int i = 1; i <= fullSolutionSize; i++) {
			/*
			 * int j = 0; for (; j < k; j++) { if (a[j] == i) break; } if (j ==
			 * k) c[l++] = i;
			 */
			if (!inPerm[i])
				solutionCandidates[l++] = i;
		}
		return l;
	}

	static public void main(String[] args) {
		int a[] = new int[NMAX];
		backtrack(a, 0, 5);
	}
}
